package com.yoso.alg;

import org.junit.jupiter.api.Test;

import java.util.*;


/**
 * 5. 最长回文子串
 * @author yoso
 * @date 2024-07-20
 */
class Solution5 {
    @Test
    public void test(){
        String s = "aacabdkacaa";
        System.out.println(longestPalindrome(s));
    }
    public String longestPalindrome(String s) {
        char[] charArray = s.toCharArray();
        // 当前最长的回文字串，默认第一个字符
        String result = String.valueOf(charArray[0]);
        // 字符串的起始位置
        int start = 0;
        // 截取字符串时的fromIndex
        int from = s.length();
        // 循环条件：start还未滑动到最后 && 剩余字符的长度 > 当前回文串的长度
        while (start < s.length() && s.length() - start > result.length()) {
            char first = charArray[start];
            int right = s.lastIndexOf(first, from);
            boolean flag = true;

            if (right == -1 || right == start) {
                start++;
                from = s.length();
                continue;
            }
            for (int i = 1; i < right - start + 1; i++) {
                if (start + i > right - i) {
                    break;
                }
                if (charArray[start + i] != charArray[right - i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                String substring = s.substring(start, right + 1);
                if (substring.length() > result.length()) {
                    result = substring;
                }
                start++;
                from = s.length();
            } else {
                from = right - 1;
            }
        }
        return result;
    }

}